package cn.edu.jxau.test;

public class MaxPQ {
    
    public static void main(String[] args) {
        
        MaxPQ maxPQ = new MaxPQ();
        maxPQ.insert('P');
        maxPQ.insert('R');
        maxPQ.insert('I');
        maxPQ.insert('O');
        System.out.println(maxPQ.delMax()); //R
        maxPQ.insert('R');
        System.out.println(maxPQ.delMax()); //R
        System.out.println(maxPQ.delMax()); //P
        maxPQ.insert('I');
        System.out.println(maxPQ.delMax()); //O
        maxPQ.insert('T');
        System.out.println(maxPQ.delMax()); //T
        maxPQ.insert('Y');
        System.out.println(maxPQ.delMax()); //Y
        System.out.println(maxPQ.delMax()); //I
        System.out.println(maxPQ.delMax()); //I
        maxPQ.insert('Q');
        maxPQ.insert('U');
        maxPQ.insert('E');
        System.out.println(maxPQ.delMax()); //U
        System.out.println(maxPQ.delMax()); //Q
        System.out.println(maxPQ.delMax()); //E
        maxPQ.insert('U');
        System.out.println(maxPQ.delMax()); //U
        maxPQ.insert('E');
    }
    
    /**
     * 堆
     */
    private char[] pq;

    /**
     * 堆中元素个数
     */
    private int size;

    /**
     * 初始大小
     */
    private static final int INIT_CAPACITY = 10;

    public MaxPQ() {

        pq = new char[INIT_CAPACITY];
    }

    public void insert(char ch) {

        if (size == pq.length - 1) {
            resize(pq.length * 2);
        }
        pq[++size] = ch;
        swim(size);
    }

    private void resize(int newCapacity) {

        if (newCapacity < INIT_CAPACITY) { // 防止优先队列缩减得过小
            return;
        }
        System.out.println("resize to " + newCapacity);
        char[] tempPQ = new char[newCapacity];
        for (int i = 1; i <= size; i++) {
            tempPQ[i] = pq[i];
        }
        pq = tempPQ;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public char max() {

        if (isEmpty()) {
            throw new RuntimeException("优先队列为空");
        }
        return pq[1];
    }

    public char delMax() {

        char max = max();
        swap(1, size);
        size--;
        sink(1);
        if (size * 4 < pq.length) {
            resize(pq.length / 2);
        }
        return max;
    }

    private void swap(int i, int j) {

        char temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private void swim(int k) {

        while (k > 1 && pq[k] > pq[k / 2]) {
            swap(k, k / 2);
            k /= 2;
        }
    }

    private void sink(int k) {

        while (2 * k <= size) {

            int i = 2 * k;
            if (i < size && pq[i] < pq[i + 1]) {
                i++;
            }
            if (pq[k] >= pq[i]) {
                break;
            }
            swap(k, i);
            k = i;
        }
    }
}
